package com.hdu.other.dp.intervalDp;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/boolean-evaluation-lcci/">面试题 08.14. 布尔运算</a>
 */
public class booleanCal {


    class Solution {
        private final Map<String, int[]> CACHE = new HashMap<>();

        public int countEval(String s, int result) {
            CACHE.clear();
            int[] res = f(s, 0, s.length() - 1);
            return res[result];
        }

        /**
         * 0 - false
         * 1 - true
         *
         * @param s
         * @param l
         * @param r
         * @return
         */
        int[] f(String s, int l, int r) {
            String key = l + " " + r;
            if (CACHE.containsKey(key)) {
                return CACHE.get(key);
            }
            if (l == r) {
                int[] res = new int[2];
                res[0] = s.charAt(l) == '0' ? 1 : 0;
                res[1] = s.charAt(l) == '1' ? 1 : 0;
                CACHE.put(key, res);
                return res;
            } else {
                int f = 0;
                int t = 0;
                for (int i = l + 1; i < r; i += 2) {
                    int[] left = f(s, l, i - 1);
                    int f1 = left[0];
                    int t1 = left[1];
                    int[] right = f(s, i + 1, r);
                    int f2 = right[0];
                    int t2 = right[1];
                    if (s.charAt(i) == '&') {
                        f += f1 * f2 + f1 * t2 + t1 * f2;
                        t += t1 * t2;
                    } else if (s.charAt(i) == '|') {
                        f += f1 * f2;
                        t += t1 * t2 + t1 * f2 + f1 * t2;
                    } else if (s.charAt(i) == '^') {
                        t += t1 * f2 + f1 * t2;
                        f += t1 * t2 + f1 * f2;
                    }
                }
                int[] res = new int[2];
                res[0] = f;
                res[1] = t;
                CACHE.put(key, res);
                return res;
            }
        }
    }
}
